package com.mango.data.structure.graph;

import java.util.Map;
import java.util.Set;

/**
 * 图测试
 * @Author: mango
 * @Date: 2022/4/24 11:48 下午
 */
public class GraphTest {
    public static void main(String[] args) {
        int[][] data = {
                {1,2,3},
                {2,3,4},
                {1,3,2},
                {2,4,5},
                {3,5,1}
        };
        Graph graph = Graph.createGraph(data,true);
        // Graph graph = Graph.createGraphUnDirect(data);
        Vertex vertex = graph.vertexs.get("1");
        Set<Vertex> dfsSet = graph.dfs(vertex);
        System.out.print("dfs:");
        dfsSet.forEach(e->{
            System.out.print(e.value+"->");
        });
        System.out.println();
        Set<Vertex> bfsSet = graph.bfs(vertex);
        System.out.print("bfs:");
        bfsSet.forEach(e->{
            System.out.print(e.value+"->");
        });
        System.out.println();
        Set<Vertex> poloSet = graph.kahnPololog();
        if(null == poloSet){
            System.out.println("不是有向无环图，无法完成拓扑排序");
        }else {
            System.out.print("kahn polo:");
            poloSet.forEach(e -> {
                System.out.print(e.value + "->");
            });
        }
        System.out.println();

        Set<Edge> primMST = graph.primMST();
        System.out.println("prim mst edge:");
        primMST.forEach(e -> {
            System.out.println("edge: "+e.from.value+"->"+e.to.value+"的weight="+e.weight);
        });

        Set<Edge> kruskalMST = graph.kruskalMST();
        System.out.println("kruskal mst edge:");
        kruskalMST.forEach(e -> {
            System.out.println("edge: "+e.from.value+"->"+e.to.value+"的weight="+e.weight);
        });

        // String[] arrows = {">>v",">>v","^<<"};
        String[] arrows = {">>v","v^<","<><"};
        // 获取无向图
        Graph arrowGraph = Graph.createGraphFromArrowString(arrows,true);
        Vertex start = arrowGraph.vertexs.get("1");
        Vertex end = arrowGraph.vertexs.get("7");
        Map<Vertex, Integer> startMap = arrowGraph.dijkstra(start);
        Map<Vertex, Integer> endMap = arrowGraph.dijkstra(end);

    }
}
